package com.cute.leetcode.editor.cn.teacher;

import java.util.Arrays;

/**
 *  计数排序 马士兵版本
 */
public class CountSortM {


    public static void main(String[] args) {

        int [] arr={2,4,2,3,7,1,1,0,0,5,6,9,8,5,7,4,0,9};

        int[] result=sort(arr);

        System.out.println(Arrays.toString(result));
    }

    private static int[] sort(int[] arr) {
        int [] newResult=new int[arr.length];

        int[] count=new int[10];

        for (int i=0;i<arr.length;i++){
            count[arr[i]]++;
        }
        for (int i=0,j=0;i<count.length;i++){
            while (count[i]-->0) newResult[j++]=i;
        }

        return newResult;
    }
}
